Monument Valley is part of the Colorado Plateau. During the Eocene epoch of the Cenozoic era, huge quantities of these rocky mountain sediments were deposited in the section of land that now contains Monument Valley. At the same time, a regional uplift occurred on the Colorado Plateau. The plateau was pushed upward by pressure from below. It broke and cracked, thus creating a new cycle of crosion. Most of the breaking was done underground long before the rocks were revealed.
The base of the rock is made up of what's called "Organ Rock Shale". This is the soft rock shale. The middle section is made up of "DeChelly Sandstone". This is the hard rock shale. At the top of the rock is called "Shinarump". The Shinarump is made up of mountain sediments that were deposited during the Cenzoic era. The rocks that you see out there have what are called joints. Joints are vertical, very smooth and even, it determines how a rock erodes. If you look at the base of the rock, you will notice a slight change of color, that part was eroded away. It was part of the "DeChelly" formation.
A mesa does not start out as a mesa, it begins to emerge when a succession of hard and soft layers is cut into by a river or brought up by a fault. The mesa becomes a butte, then becomes a spire, and then it disappears.